home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8374 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.9 KB
  1. Path: info.ucla.edu!agate!kaskel
  2. From: kaskel@kirkuk.berkeley.edu (Bruce Kaskel)
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 17 Feb 1996 10:38:03 GMT
  6. Organization: U.C. Berkeley Math. Department.
  7. Message-ID: <4g4b6b$mls@agate.berkeley.edu>
  8. References: <4fr8be$ass@news.iconn.net>
  9. NNTP-Posting-Host: kirkuk.berkeley.edu
  10.  
  11. In article <4fr8be$ass@news.iconn.net>, The Crow <thecrow@iconn.net> wrote:
  12. >Here is what I am trying to do, I want to find the last NON-ZERO digit of a 
  13. >given factorial.  For instance,
  14. >
  15. >5! = 120
  16. >
  17. >so the last non-zero digit is 2.  I want to be able to do this up to 1000.  
  18. >Problem is, no matter how huge of a data-type you use, there isn't any way for 
  19. >the computer to handle 1000!, it is however possible to find the last non-zero 
  20. >digit somehow.  One thing I have tried is as I went through mulitplying the 
  21. >series of numbers in the factorial (5 * 4 * 3 * 2) I would remove all the 
  22. >trailing ZEROS, I got this to work up to 789, but it wont work with 1000 and i 
  23. >am not really sure why.  If anyone has a clue how I can do this let me know.
  24. >
  25. >-- 
  26. >The Crow - thecrow@iconn.net
  27. >"It can't rain all the time"
  28. >-Kryptology
  29. >
  30.  
  31. One article in this thread was recently posted to sci.math where I responded.
  32. I don't know why it didn't show up here, but here was my response.
  33.  
  34.  
  35. I don't see this as a hard problem. Of course, you don't need to work
  36. with n!. In fact, you only need to keep a few bytes of data.
  37.  
  38. =========================================================================
  39.  
  40. One can keep track of rightmost nonzero digit by storing two things:
  41.  
  42. A) the number of factors of 2 which have not been ``canceled'' by a 5.
  43.  
  44.                                *
  45. B) The relavant unit in (Z/10Z)  .
  46.  
  47. =========================================================================
  48.  
  49. Here is some simple code:
  50.  
  51. int foo(n)
  52. int n;   /* the input is n for n! */
  53. {
  54. int i,j,u=1,t=0;
  55. for(i=1;i<=n;i++)
  56.   {
  57.     j=i;
  58.     while(!(j&1)) {j>>=1;t++;}
  59.     while(!(j%5)) {j/=5;t--;}
  60.     u=(u*(j%10))%10;
  61.   }
  62. if(t) {t&=3;if(!t) t=4;}          /* if t>0, only need t mod 4 */
  63. for(i=0;i<t;i++) u=(u<<1)%10;     /* include factors of 2 */
  64. return(u); /* The rightmost non-zero digit of n! is u */
  65. }
  66.  
  67.  
  68. For very large n you might have to be more careful about overflow in t.
  69. But you only really need to keep track of t mod 4 once t is positive (but
  70. you need to be able to distinguish t=0 for when n<2 or take care of these
  71. few cases separately).
  72.  
  73. It would seem that faster methods could be achieved by looping over 
  74. the primes p<n instead of all numbers <n. Indeed, primes congruent to
  75. 1 (mod 10) could be skipped altogether (this is 25% of primes). I'll
  76. elaborate on this idea if someone wants to hear it.
  77.  
  78. One thing, I usually read sci.math and not these comp.* groups. So e-mail
  79. any questions. Thanks.
  80.  
  81. --Bruce Kaskel
  82. kaskel@math.berkeley.du
  83.  
  84.